package com.gitee.feizns.explore.data_structure.graph;

import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

/**
 * 743. 网络延迟时间
 * 
 * @author feizns
 * @since 2020/5/7
 */
public class NetworkDelayTime {

    //[[2,4,10],[5,2,38],[3,4,33],[4,2,76],[3,2,64],[1,5,54],[1,4,98],[2,3,61],[2,1,0],[3,5,77],[5,1,34],[3,1,79],[5,3,2],[1,2,59],[4,3,46],[5,4,44],[2,5,89],[4,5,21],[1,3,86],[4,1,95]]
    //5
    //1
    public static void main(String[] args) {
        System.out.println(new NetworkDelayTime().networkDelayTime(new int[][]{{2,4,10}, {5,2,38}, {3,4,33}, {4,2,76}, {3,2,64}, {1,5,54}, {1,4,98}, {2,3,61}, {2,1,0}, {3,5,77}, {5,1,34}, {3,1,79}, {5,3,2}, {1,2,59}, {4,3,46},{5,4,44},{2,5,89},{4,5,21},{1,3,86},{4,1,95}}, 5, 1));
    }

    public int networkDelayTime(int[][] times, int N, int K) {
        init(times, N, K);
        ans[K] = 0;
        visited.add(K);
        dfs(K);
        int max = ans[1];
        for (int i = 2; i < ans.length; i++)
            max = Math.max(max, ans[i]);
        return visited.size() == N ? max : -1;
    }

    private void init(int[][] times, int N, int K) {
        this.graph = create(times, N + 1);
        this.ans = new int[N + 1];
        for (int i = 0; i < ans.length; i++)
            ans[i] = Integer.MAX_VALUE;
    }

    private Queue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(Comparator.comparing(Map.Entry::getKey));

    private Set<Integer> visited = new HashSet<>();

    private Graph graph;

    private int[] ans;

    private void dfs(int k) {
        Map<Integer, Integer> m = graph.graph[k];
        for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
            if ( !visited.contains(entry.getKey()) ) {
                int w = entry.getValue() + ans[k];
                ans[entry.getKey()] = Math.min(w, ans[entry.getKey()]);
                queue.add(entry);
            }
        }
        visited.add(k);
        while ( !queue.isEmpty() )
            dfs(queue.remove().getKey());
    }

    private Graph create(int[][] times, int n) {
        Graph graph = new Graph(n);
        for (int[] time : times)
            graph.add(time[0], time[1], time[2]);
        return graph;
    }

    static class Graph {
        Map[] graph;
        public Graph(int size) {
            graph = new Map[size];
            for (int i = 0; i < size; i++)
                graph[i] = new HashMap();
        }
        public void add(int s, int t, int w) {
            graph[s].put(t, w);
        }
        public int size() {
            return graph.length;
        }
    }

}
